#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2022/04/11
# @Author   :Changshu
# @File     :Exercise94.py
# 94. 二叉树的中序遍历
from typing import Optional


class TreeNode:
	def __init__(self,val=0,left=None,right=None):
		self.val=val
		self.left=left
		self.right=right


class Solution:
	def inorderTraversal(self,root:Optional[TreeNode]):
		def inorder(root:TreeNode):
			if not root:
				return
			inorder(root.left)
			r.append(root.val)
			inorder(root.right)
		r=[]
		inorder(root)
		return r

	def inorderTraversal2(self,root):
		r,nodes=[],[]
		node=root
		while node or len(nodes):
			while node:
				nodes.append(node)
				node=node.left
			node=nodes.pop()
			r.append(node.val)
			node=node.right
		return r

if __name__ == '__main__':
	s=Solution()
	node1=TreeNode(4)
	node2=TreeNode(2)
	node3 = TreeNode(7)
	node4 = TreeNode(3)
	node5 = TreeNode(9)
	node6 = TreeNode(8)
	node7 = TreeNode(5)
	node8 = TreeNode(10)
	node1.left=node2
	node1.right=node6
	node2.left=node3
	node2.right=node4
	node3.right=node5
	node6.left=node7
	node7.right=node8
	r=s.inorderTraversal2(node1)
	print(r)
